package com.aliwo.algorithm.easy;

import java.util.Arrays;

/**
 * 冒泡排序.
 * 思想：交换排序，比较相邻两个元素的大小，然后进行交换，平均时间复杂度 On*n
 *
 * @author Xu Yayuan
 * @date 2022/3/10
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] nums = {6, 4, 7, 5, 1, 3, 2};
        System.out.println("排序前元素:");
        Arrays.stream(nums).forEach(System.out::print);
        System.out.println("-------");

        int[] result = bubbleSort(nums);
        System.out.println("排序后元素:");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
        }
    }

    public static int[] bubbleSort(int[] nums) {
        int temp; // 开辟一个临时空间，存放交换的中间值
        int len = nums.length - 1; // 控制内存循环
        int tempPosition = 0; // 记录最后一次交换的位置
        // 第一层循环控制趟数, 保证第i小的元素让它归位
        for (int i = 0; i < nums.length - 1; i++) {
            int flag = 1; // 设置一个标志位
            // 第二次循环控制两两比较, 保证没有归位的让他们尽量归位
            for (int j = 0; j < len; j++) {
                if (nums[j] < nums[j + 1]) { // 从大到小排序
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = 0; // 发生交换，标志位为0
                    tempPosition = j; // 记录交换的位置
                }
                System.out.format("第 %d 遍第%d 趟结果：", i + 1, j + 1);
                for (int count : nums) {
                    System.out.print(count);
                }
                System.out.println("");
            }
            len = tempPosition; // 把最后一次交换的位置给len，来控制内循环的次数
            if (1 == flag) { // 如果没有交换过元素已经有序了
                return nums;
            }
            System.out.format("第 %d 遍最终结果：", i + 1);
            for (int count : nums) {
                System.out.print(count);
            }
        }
        return nums;
    }
}
